package leetcode11_20;

import org.junit.Test;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;

/**
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
 有效字符串需满足：
 左括号必须用相同类型的右括号闭合。
 左括号必须以正确的顺序闭合。
 注意空字符串可被认为是有效字符串。

 *
 * @author shhjiang_001
 * @create 2020-03-22 17:05
 */
public class Solution20 {
    public boolean isValid(String s) {
        if (s.length() ==  0 || s == null ) return true;
        HashMap<Character, Character> map = new HashMap<>();
        map.put(')','(');
        map.put('}','{');
        map.put(']','[');
        Deque<Character> dq = new ArrayDeque<>();
        for (char ch :s.toCharArray()){
            if (ch=='('|| ch=='{'||ch=='['){
                dq.push(ch);
            }else {
                if ( dq.isEmpty() || dq.pop()!=map.get(ch)){
                    return false;
                }
            }
        }
        if (!dq.isEmpty()) return false;
        return true;
    }

    @Test
    public void test(){
        Solution20 solution20 = new Solution20();
        boolean valid = solution20.isValid("()");
        System.out.println(valid);
    }

}

